COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	/*
C00005 ENDMK
C⊗;
/*
The program defines the relation color(Map, Colors),
between a map and a list of colors, which is true if Map
is legally colored using Colors.
-- Ehud Shapiro

A map is represented using adjacency-lists, where with
each country we associate its color, and the list of
colors of its neighbours.  If the program is used in
generate-mode, i.e. to color an uncolored map, these
colors would be uninstantiated variables.  The program
would then compute all possible colorings.  For example,
the uncolored map

        ←←←←←←←←←←
        |   a    |
        |←←←←←←←←|
        |b |c |d |
        |←←|←←|←←|
        |e  |f   |
        |←←←|←←←←|

is represented by the term:
*/

map(    [country(a, A, [B, C, D]), 
         country(b, B, [A, C, E]), 
         country(c, C, [A, B, D, E, F]), 
         country(d, D, [A, B, F]), 
         country(e, E, [B, C, F]), 
         country(f, F, [C, D, E])
        ]
).

color←map([Country | Map], Colors) :-
        color←country(Country, Colors), 
        color←map(Map, Colors).

color←map([], ←Colors).

color←country(country(←Name, C, AdjacentCs), Colors) :-
        remove(C, Colors, Colors1), 
        subset(AdjacentCs, Colors1).

subset([C | Cs], Colors) :-
        remove(C, Colors, ←), 
        subset(Cs, Colors).

subset([], ←Colors).

remove(C, [C | Cs], Cs).

remove(C, [C1 | Cs], [C1 | Cs1]) :-
        remove(C, Cs, Cs1).

colors([red, green, blue, white]).

test(Map) :-
        map(Map), 
        colors(Colors), 
        color←map(Map, Colors).